#include <stdio.h>
#include <stdlib.h>

struct ListNode {
    int val;
    struct ListNode *next;
};

typedef struct Pair {
    int first;
    int second;
} Pair;

int *nextLargerNodes(struct ListNode *head, int *returnSize) {
    int len = 0;
    struct ListNode *cur = head;
    while (cur) {
        cur = cur->next;
        len++;
    }
    int *ans = (int *) calloc(len, sizeof(int));
    Pair stack[len];
    int top = 0, pos = 0;

    cur = head;
    int idx = -1;
    while (cur) {
        ++idx;
        ans[pos++] = 0;
        while (top > 0 && stack[top - 1].first < cur->val) {
            ans[stack[top--].second] = cur->val;
        }
        stack[top].first = cur->val;
        stack[top].second = idx;
        top++;
        cur = cur->next;
    }
    *returnSize = len;
    return ans;

}

int main() {
    setbuf(stdout, 0);
    int test[3] = {2,1,5};
    struct ListNode *head = malloc(sizeof(struct ListNode));
    struct ListNode *head1 = malloc(sizeof(struct ListNode));
    struct ListNode *head2 = malloc(sizeof(struct ListNode));
    head->val = 2;
    head->next = head1;
    head1->val = 1;
    head1->next = head2;
    head2->val = 5;
    head2->next = NULL;
    int retSize = 0;
    int *ret = nextLargerNodes(head, &retSize);
    for (int i = 0; i < retSize; ++i) {
        printf(" %d ", ret[i]);
    }
}

